/**
 * Creates a new UndoManager
 * 
 * @constructor
 * @param {Integer} [maxStackSize=64]
 */
function UndoManager(maxStackSize) {
	this.maxStackSize = maxStackSize || 64;

	var State = {
		UNDO : "undo",
		REDO : "redo"
	};

	var self = this;
	var undoStack = new UndoManager.CircularStack(this.maxStackSize);
	var redoStack = new UndoManager.CircularStack(this.maxStackSize);
	var undoContext = false;
	var currentAction = null;
	var currentState = null;

	var onStateChange = function() {
		if (self.stateChanged) {
			self.stateChanged();
		}
	};

	var callAction = function(action) {
		currentAction = action;
		undoContext = true;
		switch (currentState) {
		case State.UNDO:
			action.undo();
			break;
		case State.REDO:
			action.redo();
			break;
		}
		undoContext = false;
	};

	/**
	 * Register an undo operation. A call to .undo() will cause the undo
	 * function to be executed. If you omit the second argument and the undo
	 * function will cause the registration of another undo operation, then this
	 * operation will be used as the redo function.
	 * 
	 * If you provide both arguments, a call to addUndo() during an undo() or
	 * redo() will have no effect.
	 * 
	 * 
	 * @param {Function} undoFunc The function that should undo the changes.
	 * @param {Function} [redoFunc] The function that should redo the undone
	 *            changes.
	 */
	this.addUndo = function(undoFunc, redoFunc) {
		if (undoContext) {
			/**
			 * If we are currently undoing an action and don't have a redo
			 * function yet, store the undo function to the undo function, which
			 * is in turn the redo function.
			 */
			if (currentAction.redo == null && currentState == State.UNDO) {
				currentAction.redo = undoFunc;
			}
		} else {
			/**
			 * We are not undoing right now. Store the functions as an action.
			 */
			var action = {
				undo : undoFunc,
				redo : redoFunc
			};
			undoStack.push(action);
			// clear redo stack
			redoStack.clear();

			onStateChange();
		}
	};

	/**
	 * Undoes the last action.
	 */
	this.undo = function() {
		if (this.canUndo()) {
			currentState = State.UNDO;
			var action = undoStack.pop();
			callAction(action);

			if (action.redo) {
				redoStack.push(action);
			}

			onStateChange();
		}
	};

	/**
	 * Redoes the last action.
	 */
	this.redo = function() {
		if (this.canRedo()) {
			currentState = State.REDO;
			var action = redoStack.pop();
			callAction(action);

			if (action.undo) {
				undoStack.push(action);
			}

			onStateChange();
		}
	};

	/**
	 * 
	 * @returns {Boolean} true if undo is possible, false otherwise.
	 */
	this.canUndo = function() {
		return !undoStack.isEmpty();
	};

	/**
	 * 
	 * @returns {Boolean} true if redo is possible, false otherwise.
	 */
	this.canRedo = function() {
		return !redoStack.isEmpty();
	};

	/**
	 * Resets this instance of the undo manager.
	 */
	this.reset = function() {
		undoStack.clear();
		redoStack.clear();
		undoContext = false;
		currentAction = null;
		currentState = null;

		onStateChange();
	};

	/**
	 * Event that is fired when undo or redo state changes.
	 * 
	 * @event
	 */
	this.stateChanged = function() {
	};
}

/**
 * Creates a new CircularStack. This is a stack implementation backed by a
 * circular buffer where the oldest entries automatically are overwritten when
 * new items are pushed onto the stack and the maximum size has been reached.
 * 
 * @constructor
 * @param {Integer} [maxSize=32]
 */
UndoManager.CircularStack = function(maxSize) {
	this.maxSize = maxSize || 32;
	this.buffer = [];
	this.nextPointer = 0;
};

/**
 * Pushes a new item onto the stack.
 * 
 * @param {Any} item
 */
UndoManager.CircularStack.prototype.push = function(item) {
	this.buffer[this.nextPointer] = item;
	this.nextPointer = (this.nextPointer + 1) % this.maxSize;
};

/**
 * Checks whether the stack is empty.
 * 
 * @returns {Boolean} true if empty, false otherwise.
 */
UndoManager.CircularStack.prototype.isEmpty = function() {
	if (this.buffer.length === 0) {
		return true;
	}

	var prevPointer = this.getPreviousPointer();
	if (prevPointer === null) {
		return true;
	} else {
		return this.buffer[prevPointer] === null;
	}
};

/**
 * Gets the position of the previously inserted item in the buffer.
 * 
 * @private
 * @returns {Integer} the previous pointer position or null if no previous
 *          exists.
 */
UndoManager.CircularStack.prototype.getPreviousPointer = function() {
	if (this.nextPointer > 0) {
		return this.nextPointer - 1;
	} else {
		if (this.buffer.length < this.maxSize) {
			return null;
		} else {
			return this.maxSize - 1;
		}
	}
};

/**
 * Clears the stack.
 */
UndoManager.CircularStack.prototype.clear = function() {
	this.buffer.length = 0;
	this.nextPointer = 0;
};

/**
 * Returns and removes the top most item of the stack.
 * 
 * @returns {Any} the last inserted item or null if stack is empty.
 */
UndoManager.CircularStack.prototype.pop = function() {
	if (this.isEmpty()) {
		return null;
	}

	var previousPointer = this.getPreviousPointer();
	var item = this.buffer[previousPointer];
	this.buffer[previousPointer] = null;
	this.nextPointer = previousPointer;

	return item;
};

/**
 * Returns but not removes the top most item of the stack.
 * 
 * @returns {Any} the last inserted item or null if stack is empty.
 */
UndoManager.CircularStack.prototype.peek = function() {
	if (this.isEmpty()) {
		return null;
	}
	return this.buffer[this.getPreviousPointer()];
};